/****************************************************************************
 *
 *   Copyright (C) 2019-2024 PX4 Development Team. All rights reserved.
 *   Adapted for FreeRTOS/STM32 by MicoAir Team.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 * 3. Neither the name PX4 nor the names of its contributors may be
 *    used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 ****************************************************************************/

/**
 * @file intrusive_queue.h
 * @brief Intrusive queue data structure for PX4 work queue system
 * 
 * An intrusive queue is a linked list where the link pointers are embedded
 * in the data structure itself, rather than allocated separately. This has
 * several advantages:
 * - Zero memory allocation (suitable for real-time systems)
 * - O(1) insertion and removal
 * - Cache-friendly (data and links are together)
 * 
 * Usage:
 * 1. Define your data structure with an intrusive_queue_node_t member
 * 2. Initialize the queue with intrusive_queue_init()
 * 3. Use intrusive_queue_push() to add items
 * 4. Use intrusive_queue_pop() to remove items
 * 
 * Example:
 * @code
 * typedef struct {
 *     int data;
 *     intrusive_queue_node_t node;  // Must be a member
 * } my_item_t;
 * 
 * intrusive_queue_t queue;
 * intrusive_queue_init(&queue, offsetof(my_item_t, node));
 * 
 * my_item_t item;
 * item.data = 42;
 * intrusive_queue_push(&queue, &item);
 * 
 * my_item_t *retrieved = intrusive_queue_pop(&queue);
 * @endcode
 */

#pragma once

#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief Intrusive queue node
 * 
 * This structure must be embedded in any data structure that will be
 * stored in an intrusive queue.
 */
typedef struct intrusive_queue_node {
    struct intrusive_queue_node *next;  /**< Pointer to next node */
} intrusive_queue_node_t;

/**
 * @brief Intrusive queue
 * 
 * A FIFO queue where nodes are embedded in the data structures.
 */
typedef struct {
    void *head;              /**< Pointer to first item (user data structure) */
    void *tail;              /**< Pointer to last item (user data structure) */
    size_t node_offset;      /**< Offset of intrusive_queue_node_t in user structure */
} intrusive_queue_t;

/**
 * @brief Initialize an intrusive queue
 * 
 * @param queue Pointer to queue structure
 * @param node_offset Offset of intrusive_queue_node_t in user data structure
 *                    (use offsetof() macro)
 */
void intrusive_queue_init(intrusive_queue_t *queue, size_t node_offset);

/**
 * @brief Check if queue is empty
 * 
 * @param queue Pointer to queue structure
 * @return true if queue is empty, false otherwise
 */
bool intrusive_queue_empty(const intrusive_queue_t *queue);

/**
 * @brief Get the first item in the queue (without removing it)
 * 
 * @param queue Pointer to queue structure
 * @return Pointer to first item, or NULL if queue is empty
 */
void *intrusive_queue_front(const intrusive_queue_t *queue);

/**
 * @brief Get the last item in the queue (without removing it)
 * 
 * @param queue Pointer to queue structure
 * @return Pointer to last item, or NULL if queue is empty
 */
void *intrusive_queue_back(const intrusive_queue_t *queue);

/**
 * @brief Get the number of items in the queue
 * 
 * @param queue Pointer to queue structure
 * @return Number of items in queue
 * @note This is an O(n) operation
 */
size_t intrusive_queue_size(const intrusive_queue_t *queue);

/**
 * @brief Add an item to the end of the queue
 * 
 * @param queue Pointer to queue structure
 * @param item Pointer to item to add
 * @note The item must not already be in a queue
 */
void intrusive_queue_push(intrusive_queue_t *queue, void *item);

/**
 * @brief Remove and return the first item from the queue
 * 
 * @param queue Pointer to queue structure
 * @return Pointer to removed item, or NULL if queue is empty
 */
void *intrusive_queue_pop(intrusive_queue_t *queue);

/**
 * @brief Remove a specific item from the queue
 * 
 * @param queue Pointer to queue structure
 * @param item Pointer to item to remove
 * @return true if item was found and removed, false otherwise
 */
bool intrusive_queue_remove(intrusive_queue_t *queue, void *item);

#ifdef __cplusplus
}
#endif

